//
// Created by 10462397 on 2021/7/23.
//

#include "../../common.h"

class MaxPq {

private:
    int *heap;
    int num;
    int maxSize;

    bool less(int i, int j) { return heap[i] < heap[j]; }

    void swap(int i, int j) {
        int t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

    void swim(int k) {
        int p;
        while (k > 0 && less(p = (k - 1) / 2, k)) {
            swap(p, k);
            k = p;
        }
    }

    void sink(int k) {
        int lc;
        while ((lc = (k * 2 + 1)) < num) {
            int bigger = (less(lc, lc + 1) && (lc + 1) < num) ? lc + 1 : lc;
            if (less(bigger, k)) break;
            swap(bigger, k);
            k = bigger;
        }
    }

public:
    MaxPq(int num);

    int size();

    void insert(int a);

    int delMax();

    void printHeap();
};

MaxPq::MaxPq(int maxSize) {
    this->maxSize = maxSize;
    heap = new int[maxSize + 1];
    num = 0;
}

int MaxPq::size() {
    return num;
}

void MaxPq::insert(int a) {
    heap[num++] = a;
    swim(num - 1);
    // 最后一个不一定是最小的
//    if (num > maxSize) {
//        num = maxSize;
//        heap[num] = -1;
//    }
}

int MaxPq::delMax() {
    if (num < 1) {
        return 0;
    }
    int pop = heap[0];
    heap[0] = heap[--num];
    sink(0);
    return pop;
}

void MaxPq::printHeap() {
    for (int i = 0; i < num; ++i) {
        cout << heap[i] << ",";
    }
    cout << endl;
}

class Solution {
public:
    int findKthLargest(vector<int> &nums, int k) {

        MaxPq maxPq(nums.size());
        for (int i: nums) {
            maxPq.insert(i);
        }
        MaxPq maxPq2(k);
        while (k--) {
            maxPq2.insert(-maxPq.delMax());
        }
        return -maxPq2.delMax();
    }
};


int main() {
    vector<int> arr{3,2,3,1,2,4,5,5,6};
    cout << Solution().findKthLargest(arr, 4) << endl;
}